链接：https://leetcode.cn/problems/merge-sorted-array/submissions/451443249/
//解法1
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> tmp;
        int i = 0, j = 0;
        
        //两两比较
        while (i < m  && j <  n)
        {
            if (nums1[i] <= nums2[j])
            {
                tmp.push_back(nums1[i++]);
            }
            else
            {
                tmp.push_back(nums2[j++]);
            }
        }

        //剩下的直接合并
        while (i < m) {tmp.push_back(nums1[i++]);}
        while (j < n) {tmp.push_back(nums2[j++]);}

        //交换
        nums1.swap(tmp);
        //时间和空间复杂度O（M+N）
    }
};

//解法2：(从后往前比较覆盖)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int* p1 = nums1 + m - 1, *p2 = nums2 + n - 1, *p = nums1 + m + n -1;
    while (p1 >= nums1 && p2 >= nums2)
    {
        if (*p1 > *p2)
        {
            *p = *p1;
            p1--;
        }
        else
        {
            *p = *p2;
            p2--;
        }
        p--;
    }

    if (p1 < nums1)
    {
        while (p >= nums1)
        {
            *p = *p2;
            p--;
            p2--;
        }
    }
    
}